On Solving a Generalized Chinese Remainder Theorem in the Presence of Remainder Errors

摘要

In estimating frequencies given that the signal waveforms are undersampledmultiple times, Xia et. al. proposed to use a generalized version of Chineseremainder Theorem (CRT), where the moduli are $M_1, M_2, \cdots, M_k$ which arenot necessarily pairwise coprime. If the errors of the corrupted remainders arewithin $\tau=\sds \max_{1\le i\le k} \min_{\stackrel{1\le j\le k}{j\neq i}}\frac{\gcd(M_i,M_j)}4$, their schemes can be used to construct an approximationof the solution to the generalized CRT with an error smaller than $\tau$.Accurately finding the quotients is a critical ingredient in their approach. Inthis paper, we shall start with a faithful historical account of thegeneralized CRT. We then present two treatments of the problem of solvinggeneralized CRT with erroneous remainders. The first treatment follows theroute of Wang and Xia to find the quotients, but with a simplified process. Thesecond treatment considers a simplified model of generalized CRT and takes adifferent approach by working on the corrupted remainders directly. Thisapproach also reveals some useful information about the remainders byinspecting extreme values of the erroneous remainders modulo $4\tau$. Both ofour treatments produce efficient algorithms with essentially optimalperformance. Finally, this paper constructs a counterexample to prove thesharpness of the error bound $\tau$.